1. Field of the Invention
The invention pertains to data compression, and more particularly to apparatus and methods for lossless data compression.
2. Background of the Invention
Dictionary coding is a class of compression techniques characterized by the replacement of groups of consecutive characters, or "phrases," occurring in the data, or "text," with indexes into some dictionary. The selection of entries for the coding dictionary is an important consideration in the design of a dictionary scheme, and the choice of phrases may be made staticly, semiadaptively, or adaptively. A particularly useful class of compression methods based on an adaptive scheme is known as Ziv-Lempel ("LZ") coding, which essentially involves replacing phrases with a pointer to where they have occurred earlier in the text. Dictionary techniques, including LZ coding, are described in detail in T. C. Bell, J. G. Cleary, and I. H. Witten, Text Compression, Prentice Hall, Englewood Cliffs, N.J., USA, 1990, pp. 206-243, and are incorporated herein by reference.
Dictionary techniques are useful for their speed and economy of memory. Typically, a serial, hashing search method is employed. Unfortunately, in some applications even dictionary techniques implemented with a serial hashing search method are not as fast as desired.